HashtableLookup

根据输入的键值在已排序的键数组中执行二分查找，返回对应的字符串值以及查找命中标记。

虽然名为 HashtableLookup，但实际使用二分查找（bsearch）算法，而非哈希表。要求 keys_tensor 必须已按升序排序。

\[\begin{split}\forall i \in [0, input\_size), \quad \begin{cases} \text{if } \exists j \in [0, keys\_size) \text{ s.t. } keys[j] = input[i], & \begin{cases} output[i] \leftarrow values[j] \\ hits[i] \leftarrow 1 \end{cases} \\[10pt] \text{else}, & \begin{cases} output[i] \leftarrow \text{空字符串} \\ hits[i] \leftarrow 0 \end{cases} \end{cases}\end{split}\]
输入：

  • input_tensor - 要查找的键数组地址（int32类型）。

  • keys_tensor - 已排序的键数组地址（int32类型，必须按升序排序）。

  • values_tensor - 值数组地址（字符串tensor，与keys_tensor一一对应）。

  • input_size - 输入键数组的元素个数。

  • keys_size - 键数组的元素个数（等于values_tensor中字符串的个数）。

  • core_mask（可选） - 核掩码（仅适用于共享存储版本）。

输出：

  • output_tensor - 查找结果输出地址（字符串tensor，与input_tensor长度相同）。

  • hits_tensor - 命中标记输出地址（uint8类型，1表示找到，0表示未找到）。

支持平台：

FT78NE MT7004

备注

  • FT78NE 支持int32键类型，字符串值类型

  • MT7004 支持int32键类型，字符串值类型

  • keys_tensor 必须已按升序排序，否则查找结果不正确

  • 使用二分查找算法，时间复杂度为 O(log n)

  • 如果查找失败，output_tensor 对应位置为空字符串，hits_tensor 对应位置为0

共享存储版本：

void i32_hashtablelookup_s(int *input_tensor, int *keys_tensor, void *values_tensor, void *output_tensor, uint8_t *hits_tensor, int input_size, int keys_size, int core_mask)

C调用示例：

 1//FT78NE示例
 2#include <stdio.h>
 3#include <hashtablelookup.h>
 4
 5int main(int argc, char* argv[]) {
 6    int *input_tensor = (int *)0xA0000000;   //input在DDR空间
 7    int *keys_tensor = (int *)0xB0000000;    //已排序的键数组
 8    void *values_tensor = (void *)0xC0000000;        //字符串值数组
 9    void *output_tensor = (void *)0xD0000000;        //输出字符串数组
10    uint8_t *hits_tensor = (uint8_t *)0xE0000000;    //命中标记数组
11    int input_size = 100;                            //输入键的个数
12    int keys_size = 50;                              //键值对的个数
13    int core_mask = 0xff;
14
15    i32_hashtablelookup_s(input_tensor, keys_tensor, values_tensor,
16                          output_tensor, hits_tensor, input_size,
17                          keys_size, core_mask);
18    return 0;
19}

私有存储版本：

void i32_hashtablelookup_p(int *input_tensor, int *keys_tensor, void *values_tensor, void *output_tensor, uint8_t *hits_tensor, int input_size, int keys_size)

C调用示例：

 1//FT78NE示例
 2#include <stdio.h>
 3#include <hashtablelookup.h>
 4
 5int main(int argc, char* argv[]) {
 6    int *input_tensor = (int *)0x10810000;   //input在L2空间
 7    int *keys_tensor = (int *)0x10820000;    //已排序的键数组
 8    void *values_tensor = (void *)0x10830000;        //字符串值数组
 9    void *output_tensor = (void *)0x10840000;        //输出字符串数组
10    uint8_t *hits_tensor = (uint8_t *)0x10850000;    //命中标记数组
11    int input_size = 100;                            //输入键的个数
12    int keys_size = 50;                              //键值对的个数
13
14    i32_hashtablelookup_p(input_tensor, keys_tensor, values_tensor,
15                          output_tensor, hits_tensor, input_size,
16                          keys_size);
17    return 0;
18}